P2P B&B and GA for the Flow-Shop Scheduling Problem
Identifieur interne : 004340 ( Main/Exploration ); précédent : 004339; suivant : 004341P2P B&B and GA for the Flow-Shop Scheduling Problem
Auteurs : A. Bendjoudi [Algérie] ; S. Guerdah [Algérie] ; M. Mansoura [Algérie] ; N. Melab [France] ; E. G. Talbi [France]Source :
- Studies in Computational Intelligence [ 1860-949X ]
Abstract
Summary: Solving exactly Combinatorial Optimization Problems (COPs) using a Branch-and-Bound algorithm (B&B) requires a huge amount of computational resources. The efficiency of such algorithm can be improved by its hybridization with meta-heuristics such as Genetic Algorithms (GA) which proved their effectiveness, since they generate acceptable solutions in a reasonable time. Moreover, distributing at large scale the computation, using for instance Peer-to-Peer (P2P) Computing, provides an efficient way to reach high computing performance. In this chapter, we propose ParallelBB and ParallelGA, which are P2P-based parallelization of the B&B and GA algorithms for the computational Grid. The two algorithms have been implemented using the ProActive distributed object Grid middleware. The algorithms have been applied to a mono-criterion permutation flow-shop scheduling problem and promisingly experimented on the Grid5000 computational Grid.
Url:
DOI: 10.1007/978-3-540-69277-5_11
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: 002C58
- to stream Istex, to step Curation: 002C21
- to stream Istex, to step Checkpoint: 000D68
- to stream Main, to step Merge: 004451
- to stream Main, to step Curation: 004340
Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">P2P B&B and GA for the Flow-Shop Scheduling Problem</title><author><name sortKey="Bendjoudi, A" sort="Bendjoudi, A" uniqKey="Bendjoudi A" first="A." last="Bendjoudi">A. Bendjoudi</name></author><author><name sortKey="Guerdah, S" sort="Guerdah, S" uniqKey="Guerdah S" first="S." last="Guerdah">S. Guerdah</name></author><author><name sortKey="Mansoura, M" sort="Mansoura, M" uniqKey="Mansoura M" first="M." last="Mansoura">M. Mansoura</name></author><author><name sortKey="Melab, N" sort="Melab, N" uniqKey="Melab N" first="N." last="Melab">N. Melab</name></author><author><name sortKey="Talbi, E G" sort="Talbi, E G" uniqKey="Talbi E" first="E. G." last="Talbi">E. G. Talbi</name></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:BBAEC76F82A67C0D88E1D0E9A164AF9CC9457842</idno><date when="2008" year="2008">2008</date><idno type="doi">10.1007/978-3-540-69277-5_11</idno><idno type="url">https://api.istex.fr/ark:/67375/HCB-DB6FK1MX-K/fulltext.pdf</idno><idno type="wicri:Area/Istex/Corpus">002C58</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">002C58</idno><idno type="wicri:Area/Istex/Curation">002C21</idno><idno type="wicri:Area/Istex/Checkpoint">000D68</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">000D68</idno><idno type="wicri:doubleKey">1860-949X:2008:Bendjoudi A:p:p:b</idno><idno type="wicri:Area/Main/Merge">004451</idno><idno type="wicri:Area/Main/Curation">004340</idno><idno type="wicri:Area/Main/Exploration">004340</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">P2P B&B and GA for the Flow-Shop Scheduling Problem</title><author><name sortKey="Bendjoudi, A" sort="Bendjoudi, A" uniqKey="Bendjoudi A" first="A." last="Bendjoudi">A. Bendjoudi</name><affiliation wicri:level="3"><country xml:lang="fr">Algérie</country><wicri:regionArea>Département d’Informatique CEntre de Recherche sur l’Information Scientifique et Technique (CERIST), Laboratoire d’Ingénierie et Théories des Systèmes Informatiques, Université A/Mira de Béjaia, Algiers</wicri:regionArea><placeName><settlement type="city">Alger</settlement><region nuts="2">Wilaya d'Alger</region></placeName></affiliation><affiliation></affiliation></author><author><name sortKey="Guerdah, S" sort="Guerdah, S" uniqKey="Guerdah S" first="S." last="Guerdah">S. Guerdah</name><affiliation wicri:level="1"><country xml:lang="fr">Algérie</country><wicri:regionArea>Département Informatique, Université Mouloud Mammeri de Tizi Ouzou, Tizi Ouzou</wicri:regionArea><wicri:noRegion>Tizi Ouzou</wicri:noRegion></affiliation><affiliation></affiliation></author><author><name sortKey="Mansoura, M" sort="Mansoura, M" uniqKey="Mansoura M" first="M." last="Mansoura">M. Mansoura</name><affiliation wicri:level="1"><country xml:lang="fr">Algérie</country><wicri:regionArea>Département Informatique, Université Mouloud Mammeri de Tizi Ouzou, Tizi Ouzou</wicri:regionArea><wicri:noRegion>Tizi Ouzou</wicri:noRegion></affiliation><affiliation></affiliation></author><author><name sortKey="Melab, N" sort="Melab, N" uniqKey="Melab N" first="N." last="Melab">N. Melab</name><affiliation wicri:level="3"><country xml:lang="fr">France</country><wicri:regionArea>Laboratoire d’Informatique Fondamentale de Lille LIFL, Université des Sciences et Technologies de Lille, France, UMR CNRS 8022, Cité scientifique INRIA Futurs - DOLPHIN, 59655, Villeneuve d’Ascq cedex</wicri:regionArea><placeName><region type="region" nuts="2">Hauts-de-France</region><region type="old region" nuts="2">Nord-Pas-de-Calais</region><settlement type="city">Villeneuve d’Ascq</settlement></placeName></affiliation><affiliation wicri:level="1"><country wicri:rule="url">France</country></affiliation></author><author><name sortKey="Talbi, E G" sort="Talbi, E G" uniqKey="Talbi E" first="E. G." last="Talbi">E. G. Talbi</name><affiliation wicri:level="3"><country xml:lang="fr">France</country><wicri:regionArea>Laboratoire d’Informatique Fondamentale de Lille LIFL, Université des Sciences et Technologies de Lille, France, UMR CNRS 8022, Cité scientifique INRIA Futurs - DOLPHIN, 59655, Villeneuve d’Ascq cedex</wicri:regionArea><placeName><region type="region" nuts="2">Hauts-de-France</region><region type="old region" nuts="2">Nord-Pas-de-Calais</region><settlement type="city">Villeneuve d’Ascq</settlement></placeName></affiliation><affiliation wicri:level="1"><country wicri:rule="url">France</country></affiliation></author></analytic><monogr></monogr><series><title level="s" type="main" xml:lang="en">Studies in Computational Intelligence</title><idno type="ISSN">1860-949X</idno><idno type="eISSN">1860-9503</idno><idno type="ISSN">1860-949X</idno></series></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">1860-949X</idno></seriesStmt></fileDesc><profileDesc><textClass></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Summary: Solving exactly Combinatorial Optimization Problems (COPs) using a Branch-and-Bound algorithm (B&B) requires a huge amount of computational resources. The efficiency of such algorithm can be improved by its hybridization with meta-heuristics such as Genetic Algorithms (GA) which proved their effectiveness, since they generate acceptable solutions in a reasonable time. Moreover, distributing at large scale the computation, using for instance Peer-to-Peer (P2P) Computing, provides an efficient way to reach high computing performance. In this chapter, we propose ParallelBB and ParallelGA, which are P2P-based parallelization of the B&B and GA algorithms for the computational Grid. The two algorithms have been implemented using the ProActive distributed object Grid middleware. The algorithms have been applied to a mono-criterion permutation flow-shop scheduling problem and promisingly experimented on the Grid5000 computational Grid.</div></front></TEI><affiliations><list><country><li>Algérie</li><li>France</li></country><region><li>Hauts-de-France</li><li>Nord-Pas-de-Calais</li><li>Wilaya d'Alger</li></region><settlement><li>Alger</li><li>Villeneuve d’Ascq</li></settlement></list><tree><country name="Algérie"><region name="Wilaya d'Alger"><name sortKey="Bendjoudi, A" sort="Bendjoudi, A" uniqKey="Bendjoudi A" first="A." last="Bendjoudi">A. Bendjoudi</name></region><name sortKey="Guerdah, S" sort="Guerdah, S" uniqKey="Guerdah S" first="S." last="Guerdah">S. Guerdah</name><name sortKey="Mansoura, M" sort="Mansoura, M" uniqKey="Mansoura M" first="M." last="Mansoura">M. Mansoura</name></country><country name="France"><region name="Hauts-de-France"><name sortKey="Melab, N" sort="Melab, N" uniqKey="Melab N" first="N." last="Melab">N. Melab</name></region><name sortKey="Melab, N" sort="Melab, N" uniqKey="Melab N" first="N." last="Melab">N. Melab</name><name sortKey="Talbi, E G" sort="Talbi, E G" uniqKey="Talbi E" first="E. G." last="Talbi">E. G. Talbi</name><name sortKey="Talbi, E G" sort="Talbi, E G" uniqKey="Talbi E" first="E. G." last="Talbi">E. G. Talbi</name></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 004340 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 004340 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= Main
|étape= Exploration
|type= RBID
|clé= ISTEX:BBAEC76F82A67C0D88E1D0E9A164AF9CC9457842
|texte= P2P B&B and GA for the Flow-Shop Scheduling Problem
}}
| This area was generated with Dilib version V0.6.33. |  |